package comprehensive;

import java.util.ArrayList;
import java.util.List;

public class Exercises4 {
    // 22、括号生成
    int left; // 子串中左括号的个数
    int right; // 子串中右括号的个数
    int count; // 左右括号最多出现的次数
    List<String> ret;
    StringBuilder path;

    public List<String> generateParenthesis(int n) {
        // 有效的括号是符合：1、左括号的个数 == 右括号的个数
        // 2、从头开始的子串中左括号的个数 >= 右括号的个数

        count = n;
        ret = new ArrayList<>();
        path = new StringBuilder();

        dfs();
        return ret;
    }

    public void dfs() {

        // 当右括号的个数和count相等的时候，说明这个path子串就已经添加结束了，这时候右括号的个数必然等于左括号的个数的
        if (right == count) {
            ret.add(path.toString());
            return;
        }
        // 当左括号的个数left >= count 的时候，就不可以进行再次添加左括号了，这里也就是剪枝(对左括号的剪枝)
        // 添加左括号
        if (left < count) {
            // 说明左括号还可以进行继续添加
            path.append("(");
            left++;
            //递归到下一层
            dfs();
            // 递归返回，这时候要进行回溯
            path.deleteCharAt(path.length() - 1);
            left--;
        }
        // 当右括号的数量 >= 左括号的数量的时候，就不可以进行再次添加了，这里也是剪枝(对右括号的剪枝)
        // 添加右括号
        if(right < left) {
            path.append(")");
            right++;
            //递归
            dfs();
            // 递归返回，回溯->恢复现场
            path.deleteCharAt(path.length() - 1);
            right--;
        }
    }
}
